// prog cabine telefonica.cpp
//
#include "stdafx.h"


const int num_cabines = 5;

int num_combinacoes;
int cab[ num_cabines ];


void imprime_combinacao()
{
	for( int i = 0; i < num_cabines; i++ )
		printf( "%2d ", cab[ i ] );

	printf( "\n" ); 
}

bool livre( int posic )
{
	return posic == -1 || posic == num_cabines || cab[ posic ] == 0;
}

int casas_livres( int posic )
{
	// retorna -1 se a posicao estiver ocupada ou o num de casas livres adjacentes a posicao.

	int ret = 1;

	if( !livre( posic ) )
		ret = -1;
	else if( livre( posic - 1 ) && livre( posic + 1 ) )
		ret = 2;
	else if( !livre( posic - 1 ) && !livre( posic + 1 ) )
		ret = 0;

	return ret;
}

void preenche_lista_cabines_ok( int *cabs_ok )
{
	int qtd_maiores = 0;
	int maior_qtd_livres = 0;
	int qtd_livres;

	for( int i = 0; i < num_cabines; i++ )
	{
		qtd_livres = casas_livres( i );

		if( qtd_livres > maior_qtd_livres )
		{
			qtd_maiores = 0;
			maior_qtd_livres = qtd_livres;
		}

		if( qtd_livres == maior_qtd_livres )
			cabs_ok[ ++qtd_maiores ] = i;
	}

	cabs_ok[ 0 ] = qtd_maiores;
}

void combinacoes_cabine_recursiva( int espiao )
{
	int cabs_ok[ num_cabines + 1 ];
	preenche_lista_cabines_ok( cabs_ok );

	for( int i = 1; i <= cabs_ok[ 0 ]; i++ )
	{
		int pos_cabine = cabs_ok[ i ];

		cab[ pos_cabine ] = espiao;

		if( espiao < num_cabines )
			combinacoes_cabine_recursiva( espiao + 1 );
		else
		{
			imprime_combinacao();
			num_combinacoes++;
		}

		cab[ pos_cabine ] = 0;
	}
}


int main( int argc, char* argv[] )
{
	for( int i = 0; i < num_cabines; i++ )
		cab[ i ] = 0;

	num_combinacoes = 0;

	combinacoes_cabine_recursiva( 1 );

	printf( "num. de cabines = %d -> total de combinacoes = %d", num_cabines, num_combinacoes );

	getchar();

	return 0;
}
